//给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。 
//
// 你可以假设数组是非空的，并且给定的数组总是存在多数元素。 
//
// 
//
// 示例 1: 
//
// 输入: [3,2,3]
//输出: 3 
//
// 示例 2: 
//
// 输入: [2,2,1,1,1,2,2]
//输出: 2
// 
// Related Topics 位运算 数组 分治算法 
// 👍 682 👎 0

package leetcode.editor.cn;

import java.lang.reflect.Array;
import java.util.Arrays;

//Java：多数元素
public class P169MajorityElement {
    public static void main(String[] args) {
        Solution solution = new P169MajorityElement().new Solution();
        int[] arr={6,6,6,7,7,3,4,5,2,4,7,9};
        solution.majorityElement(arr);
        // TO TEST
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        /*
         * 先排序，然后取中间元素，时间复杂度为O(nlogn)
         * */
        public int majorityElement1(int[] nums) {
            if (nums == null) {
                return -1;
            }
            Arrays.sort(nums);
            int mid = (nums.length >>> 1);
            return nums[mid];
        }

        /*
         * 使用partition函数
         * 不适用于这种情况，因为数组可能大部分有序（有很多相同的元素），时间复杂度会退化为O(n^2)。
         * */
        public int majorityElement2(int[] nums) {
            if (nums == null) {
                return -1;
            }
            int len = nums.length;
            int beign = 0, end = len - 1;
            int mid = beign + ((end - beign) >>> 1);
            int index = partition(nums, beign, end, len);
            while (index != mid) {
                if (index < mid) {
                    index = partition(nums, index + 1, end, len);
                } else {
                    index = partition(nums, beign, index - 1, len);
                }
            }
            System.out.println(mid);
            for (int e : nums
                    ) {
                System.out.print(e + " ");
            }
            System.out.println();
            System.out.println(nums[mid]);
            return nums[mid];
        }

        public int partition(int nums[], int begin, int end, int len) {
            if (begin < 0 || begin > end || end < 0 || end >= len) {
                return -1;
            }
            int small = begin - 1;
            int index = begin + (int) (Math.random() * (end - begin + 1));
            swap(nums, index, end);

            for (int i = begin; i < end; i++) {
                if (nums[i] <= nums[end]) {
                    small++;
                    if (small != i) {
                        swap(nums, i, small);
                    }
                }
            }

            small++;
            swap(nums, small, end);
            return small;
        }

        public void swap(int nums[], int i, int j) {
            int tmp = nums[i];
            nums[i] = nums[j];
            nums[j] = tmp;
        }


        /*
        * 国际站上大佬的解答
        * Boyer-Moore 投票算法
        * */

        public int majorityElement(int[] nums){
            int marjor=nums[0],count=1;
            for(int i=1;i<nums.length;i++){
                if(count==0){//已经被抵消完
                    count++;
                    marjor=nums[i];
                }else if(marjor==nums[i]){
                    count++;
                }else{
                    count--;
                }
            }

            return marjor;
        }

    }
//leetcode submit region end(Prohibit modification and deletion)

}
